package com.xcc.datastructure;

/**
 * @Description 求【最大连续子数组和】练习
 *
 * 题目描述：
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 子数组 是数组中的一个连续部分。
 * <p>
 * 示例一：
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 * <p>
 * 事例二：
 * 输入：nums = [1]
 * 输出：1
 * <p>
 * 示例三：
 * 输入：nums = [5,4,-1,7,8]
 * 输出：23
 *
 * @Author xiechuang
 * @Date 2021/12/19
 */
public class MaxSubArrayDemo {

    public static void main(String[] args) {

        // 全为负数
        int[] nums1 = new int[]{-1};
        // 预期结果：-1
        System.out.println("v1：" + maxSubArrayV1(nums1));
        System.out.println("v2：" + maxSubArrayV2(nums1));
        System.out.println("v3：" + maxSubArrayV3(nums1));

        // 全为正数
        int[] nums2 = new int[]{1, 3, 2, 4, 5};
        // 预期结果：15
        System.out.println("v1：" + maxSubArrayV1(nums2));
        System.out.println("v2：" + maxSubArrayV2(nums2));
        System.out.println("v3：" + maxSubArrayV3(nums2));

        // 正负交叉
        int[] nums3 = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
        // 预期结果：6
        System.out.println("v1：" + maxSubArrayV1(nums3));
        System.out.println("v2：" + maxSubArrayV2(nums3));
        System.out.println("v3：" + maxSubArrayV3(nums3));

    }

    /**
     * 版本一：
     * 思路：两层循环遍历记录最大值
     *
     * @param nums
     * @return
     */
    public static int maxSubArrayV1(int[] nums) {
        // 初始值，用于存储子数组最大值的和
        int max = nums[0];
        int length = nums.length;
        for(int i = 0; i < length; i++) {
            // 初始子数组和的最大值
            int childMax = nums[i];
            // 连续累加的值
            int childSum = nums[i];
            // 遍历从当前元素开始找到最大连续的和
            for(int j = i + 1; j < length; j++) {
                childSum += nums[j];
                if (childMax < childSum) {
                    childMax = childSum;
                }
            }
            if(max < childMax) {
                max = childMax;
            }
        }
        return max;
    }

    /**
     * 版本二：贪心算法
     * 思路：若当前指针指向元素之前的元素的和为负则丢弃之前的和
     *
     * @param nums
     * @return
     */
    public static int maxSubArrayV2(int[] nums) {
        int max = 0;
        // 数组长度
        int length = nums.length;
        int maxSum = nums[0];
        for (int i = 0; i < length; i++) {
            int value = nums[i];
            if (max < 0) {
                max = value;
            } else {
                max += value;
            }
            maxSum = Math.max(max, maxSum);
        }
        return maxSum;
    }

    /**
     * 版本三：动态规划
     * 思路：若前一个元素大于0，则将计算出来的前一个元素相加，最后取出相加结果集中的最大值
     *
     * @param nums
     * @return
     */
    public static int maxSubArrayV3(int[] nums) {
        int length = nums.length;
        int maxSum = nums[0];
        int before = nums[0];
        for (int i = 1; i < length; i++) {
            if (before > 0) {
                before += nums[i];
            } else {
                before = nums[i];
            }
            maxSum = Math.max(maxSum, before);
        }
        return maxSum;
    }

}
